using System;
using System.Collections.Generic;
using System.Text;

namespace Studio.Game.GameBox
{
    /// <summary>
    /// The keytree class, the core datatype enable faster searching airthmetic
    /// </summary>
    public class KeyTree<T>
    {
        private KeyTreeNode<T> _Root;
        /// <summary>
        /// Root of the keytree
        /// </summary>
        public KeyTreeNode<T> Root
        {
            get { return _Root; }
            set { _Root = value; }
        }

        /// <summary>
        /// public constructors
        /// </summary>
        public KeyTree()
        {
            _Root = new KeyTreeNode<T>();
            _Root.Data = default(T);
        }

        public KeyTree(KeyTreeNode<T> Node)
        {
            _Root = Node;
        }

        /// <summary>
        /// Build key tree from dictionary
        /// </summary>
        public KeyTree(Dictionary<string, T> Keys)
        {
            Build(Keys, default(T), false);
        }

        /// <summary>
        /// Build key tree without Data
        /// </summary>
        public KeyTree(IList<string> KeysList, bool CaseSensitive)
        {
            Build(KeysList, CaseSensitive);
        }

        /// <summary>
        /// Build key tree from dictionary
        /// </summary>
        public KeyTree(Dictionary<string, T> Keys, T Root, bool CaseSensitive)
        {
            Build(Keys, Root, CaseSensitive);
        }

        public void Build(IDictionary<string, T> Keys, T Root, bool CaseSensitive)
        {
            // Build Root
            _Root = new KeyTreeNode<T>();
            _Root.Data = Root;
            // Build Tree
            foreach(string Word in Keys.Keys)
            {
                T Data = Keys[Word];
                KeyTreeNode<T> Node = _Root;
                // Case Match Disabled. 
                string WordMod = Word;
                if (false == CaseSensitive) WordMod = Word.ToUpper();
                for (int i = 0; i < WordMod.Length; i++)
                {
                    char c = WordMod[i];
                    if (null == Node[c])
                        Node[c] = new KeyTreeNode<T>();
                    // Move next
                    Node = Node[c];
                    Node.Data = Data;
                }
                // Mark a flag to recognize this word
                Node.IsLeaf = true;
            }
        }

        public void Build(IList<string> Keys, bool CaseSensitive)
        {
            // Build Root
            _Root = new KeyTreeNode<T>();
            _Root.Data = default(T);
            // Build Tree
            foreach(string Word in Keys)
            {
                T Data = default(T);
                KeyTreeNode<T> Node = _Root;
                // Case Match Disabled. 
                string WordMod = Word;
                if (false == CaseSensitive) WordMod = Word.ToUpper();
                for (int i = 0; i < WordMod.Length; i++)
                {
                    char c = WordMod[i];
                    if (null == Node[c])
                        Node[c] = new KeyTreeNode<T>();
                    // Move next
                    Node = Node[c];
                    Node.Data = Data;
                }
                // Mark a flag to recognize this word
                Node.IsLeaf = true;
            }
        }

        /// <summary>
        /// Recognize a word
        /// </summary>
        /// <param name="Word"></param>
        /// <returns></returns>
        public bool Recognize(string Word, ref T Result)
        {
            KeyTreeNode<T> Node = _Root;

            Word = Word.ToUpper();

            for (int i = 0; i < Word.Length; i++)
            {
                char c = Word[i];
                if (null == Node[c])
                    return false;
                Node = Node[c];
            }
            // Recognize it if IsLeaf flag marked.
            Result = Node.Data;
            return Node.IsLeaf;
        }
    }
}
